package com.dyz.leetcode._10_slidingWindow;

import java.util.Arrays;

public class _567_checkInclusion {
    //计数法
    public boolean checkInclusion(String s1, String s2) {
        int n = s1.length();
        int m = s2.length();
        if(n>m){return false;}

        int[] cnt1 = new int[26];
        int[] cnt2 = new int[26];
        for (int i = 0; i < n; i++) {
            ++cnt1[s1.charAt(i)-'a'];
            ++cnt2[s2.charAt(i)-'a'];
        }
        if( Arrays.equals(cnt1, cnt2)){return true;}

        for(int i=n; i<m;i++){
            ++cnt1[s1.charAt(i)-'a'];
            --cnt2[s2.charAt(i-n)-'a'];
            if(Arrays.equals(cnt1,cnt2)){return true;}
        }
        return false;

    }

    // 滑动窗口
    public boolean checkInclusion1(String s1, String s2) {
        int n = s1.length(), m = s2.length();
        if (n > m) {
            return false;
        }

        // 先统计字符串 s1 中每个字符出现的次数
        int[] cnt = new int[26];
        for (int i = 0; i < n; ++i) {
            ++cnt[s1.charAt(i) - 'a'];
        }

        int left = 0, right = 0;
        while (right < m) {
            int x = s2.charAt(right) - 'a';
            cnt[x]--;
            while (cnt[x] < 0) {
                // 通过缩减窗口使得 cnt[x] 不为负数
                cnt[s2.charAt(left) - 'a']++;
                left++;
            }
            // 到现在为止，当前窗口中字符的 cnt 值都为 0（不包含 s1 里面的字符）
            // 如果窗口的长度等于 n 的话，那么当前窗口中的 cnt 的值都是 0
            if (right - left + 1 == n) {return true;}
            // bug 修复：right 需要往前走
            right++;
        }
        return false;
    }
}
